#include <iostream>
#include <new>

using namespace std;

class nomemory {};

class Allocator {
  typedef unsigned int word;
  struct fbhdr {
    long size;
    word *next; 
    fbhdr(long size, word *next): size(size), next(next) {}
  };
  struct obhdr {
    long size;
    obhdr(long size): size(size) {}
  };
  word *pool;
  word *ff;
  long words(long nbytes) { return (nbytes - 1) / sizeof(word) + 1; }
  public:
    Allocator(long size);
    void *alloc(long size);
    void free(void *);
    void dump();
};

Allocator::Allocator(long size)
{
  pool = new word[words(size)];
  ff = pool;
  new (pool) fbhdr(words(size), 0);
}

void * Allocator::alloc(long size) {
  long bs = max(words(size) + words(sizeof(obhdr)), words(sizeof(fbhdr))); 
  cout << "bs: " << bs << endl;
  fbhdr *b = (fbhdr *)ff; 
  word **bp = &ff;	
  while (b && b->size != bs && b->size - bs < words(sizeof(fbhdr))) {
    bp = &b->next;
    b = (fbhdr*)b->next; 
  }
  if (!b) throw nomemory();
  if (b->size == bs) {
    *bp = b->next; 
  }
  else {
    word *rest = (word *)b + bs;
    new (rest) fbhdr(b->size - bs, b->next);
    *bp = rest;
  }
  word *block = (word *) b;
  new (block) obhdr(bs); 
  return block + words(sizeof(obhdr));
}

void Allocator::free(void * addr) {
  word *ob = (word *)addr - words(sizeof(obhdr));     
  word *b = ff;
  word **bp = &ff;
  while (b && b + ((fbhdr*)b)->size != ob &&
         ob + ((obhdr*)ob)->size != b) {
      bp = &((fbhdr*)b)->next;
      b = ((fbhdr*)b)->next;
  }
  if (!b) {
    cout << "no free neighbors" << endl;
    new (ob) fbhdr(((obhdr*)ob)->size, ff);
    ff = ob;
  }
  else  if (b + ((fbhdr*)b)->size == ob) {
    cout << "merge with left" << endl; 
    ((fbhdr*)b)->size += ((obhdr*)ob)->size;
  }
  else {
    cout << "merge with right" << endl;
    new (ob) fbhdr(((obhdr*)ob)->size + ((fbhdr*)b)->size, ((fbhdr*)b)->next);
    *bp = ob; 
  }
}

void Allocator::dump() {
  cout << "===dump===" << endl;
  fbhdr *hdr = (fbhdr*)ff; 
  while (hdr) {
    cout << "addr: " << (word*)hdr - pool << ", size: " << hdr->size << endl; 
    hdr = (fbhdr *)hdr->next;
  }
}

int main()
{
  Allocator A(1024 * 1024);
  A.dump();
  void *x = A.alloc(100);
  void *y = A.alloc(100);
  void *z = A.alloc(100);
  A.dump();
  A.free(x);
  A.dump();
  A.free(y);
  A.dump();
  A.free(z);
  A.dump();
  return 0;
}
